package com.hyq.grid.algorithm;

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created by HYQ on 2020/6/30 10:04
 */
public class delaunay {
    public delaunay() {
    }

    public delaunay(List<Map<String, Double>> border) {

        this.border = border.subList(0, border.size() - 1);
        this.distance = border.get(border.size() - 1).get("Distance");
        borderPoints = new ArrayList<>();
        for (int i = 0; i < border.size() - 1; i++) {
            borderPoints.add(new Point2D.Double(border.get(i).get("X"), border.get(i).get("Y")));
        }
    }


    private static final double EPSILON = 1.0 / 1048576.0;

    private List<Map<String, Double>> border;
    private List<Point2D.Double> borderPoints;
    private double distance;

    public List<Map> getDelaunay() throws Exception {

//        寻找最大矩形范围
        Map<String, Double> bound = getBound();

        List<double[]> points = new ArrayList<>();

        double x, y;

//        添加边界点
        for (int i = 0; i < (border.size() - 1); i++) {
            double x1 = border.get(i).get("X");
            double y1 = border.get(i).get("Y");
            double x2 = border.get(i + 1).get("X");
            double y2 = border.get(i + 1).get("Y");

            points.add(new double[]{x1, y1});
            // ay+bx+c=0 (x1, y1, x2, y2)
            double a, b, c, length;
            length = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
            int count = (int) Math.floor(length / distance);
            if ((x1 - x2) == 0) {
                double tempMiny = y1;
                if (y2 < y1) tempMiny = y2;

                for (int j = 0; j < count; j++) {
                    points.add(new double[]{x1, tempMiny + distance * j});
                }
            } else {
                double xdistance = distance / (length / Math.abs(x1 - x2));
                a = 1;
                b = -(y1 - y2) / (x1 - x2);
                c = -(y1 + b * x1);

                double tempMinX = x1;

                if (x1 > x2) tempMinX = x2;

                for (int j = 0; j < count; j++) {
//                    points.push([minX + i * xdistance, -(b * (minX + i * xdistance) + c)]);
                    points.add(new double[]{tempMinX + j * xdistance, -(b * (tempMinX + j * xdistance) + c)});
                }
            }
        }
        points.add(new double[]{border.get(border.size() - 1).get("X"), border.get(border.size() - 1).get("Y")});

        //添加随机点
        for (int i = 0; i < Math.ceil((bound.get("maxY") - bound.get("minY")) / distance); i++) {
            for (int j = 0; j < Math.ceil((bound.get("maxX") - bound.get("minX")) / distance); j++) {
//                当前四边西行
                List<Point2D.Double> currentPoints = new ArrayList<>();
                currentPoints.add(new Point2D.Double(bound.get("minX") + j * distance, bound.get("minY") + i * distance));
                currentPoints.add(new Point2D.Double(bound.get("minX") + (j + 1) * distance, bound.get("minY") + i * distance));
                currentPoints.add(new Point2D.Double(bound.get("minX") + (j + 1) * distance, bound.get("minY") + (i + 1) * distance));
                currentPoints.add(new Point2D.Double(bound.get("minX") + j * distance, bound.get("minY") + (i + 1) * distance));


                for (int k = 0; k < currentPoints.size(); k++) {
//                    四边形有点在啊范围内
                    if (IsPtInPoly(currentPoints.get(k), borderPoints)) {
                        do {
                            x = Math.random() * distance + currentPoints.get(0).x;
                            y = Math.random() * distance + currentPoints.get(0).y;
                        } while (!IsPtInPoly(new Point2D.Double(x, y), borderPoints));
                        points.add(new double[]{x, y});
                        break;
                    }
                }

            }
        }



        List<Integer> point1 = triangulate(points);

        List<Map> delatri = new ArrayList<>();
        for (int i = 0; i < point1.size(); ) {
            Map<String, Object> tempMap = new HashMap<String, Object>();
            double[] xout = new double[3];
            double[] yout = new double[3];
            xout[0] = points.get(point1.get(i))[0];
            xout[1] = points.get(point1.get(i + 1))[0];
            xout[2] = points.get(point1.get(i + 2))[0];

            yout[0] = points.get(point1.get(i))[1];
            yout[1] = points.get(point1.get(i + 1))[1];
            yout[2] = points.get(point1.get(i + 2))[1];

            tempMap.put("X", xout);
            tempMap.put("Y", yout);

            delatri.add(tempMap);
            i = i + 3;
        }
        return delatri;
    }

    public List<Integer> triangulate(List<double[]> vertices) throws Exception {
        int n = vertices.size();
        int a, b, c;
        double dx, dy;
        if (n < 3) {
            return null;
        }
//        顶点索引数组
        int[] indices = new int[n];
        for (int i = (n - 1); i >= 0; i--) {
            indices[i] = i;
        }
//        将坐标的X坐标按升序排列
        for (int i = 1; i < indices.length; i++) {
            //挖出一个要用来插入的值,同时位置上留下一个可以存新的值的坑
            int x = indices[i];
            int j = i - 1;

            //在前面有一个或连续多个值比x小的时候,一直循环往前面找,将x插入到这串值前面
            while (j >= 0 && vertices.get(x)[0] > vertices.get(indices[j])[0]) {
                //当vertices[j][0]比x小的时候,将j向后移一位,正好填到坑中
                indices[j + 1] = indices[j];
                j--;
            }
            //将x插入到最前面
            indices[j + 1] = x;
        }


        List<double[]> st = supertriangle(vertices);
        vertices.addAll(st);


        List<Map> open = new ArrayList<>();
        open.add(circumcircle(vertices, n + 0, n + 1, n + 2));

        List<Integer> edges = new ArrayList<>();
        List<Map> closed = new ArrayList<>();

        for (int i = (indices.length - 1); i >= 0; i--) {
            c = indices[i];

            for (int j = (open.size() - 1); j >= 0; j--) {

                dx = vertices.get(c)[0] - Double.parseDouble(open.get(j).get("x").toString());

                if (dx > 0.0 && dx * dx > Double.parseDouble(open.get(j).get("r").toString())) {
                    closed.add(open.get(j));
                    open.remove(j);
                    continue;
                }
                dy = vertices.get(c)[1] - Double.parseDouble(open.get(j).get("y").toString());
                if (dx * dx + dy * dy - Double.parseDouble(open.get(j).get("r").toString()) > EPSILON)
                    continue;

                edges.add(Integer.parseInt(open.get(j).get("i").toString()));
                edges.add(Integer.parseInt(open.get(j).get("j").toString()));
                edges.add(Integer.parseInt(open.get(j).get("j").toString()));
                edges.add(Integer.parseInt(open.get(j).get("k").toString()));
                edges.add(Integer.parseInt(open.get(j).get("k").toString()));
                edges.add(Integer.parseInt(open.get(j).get("i").toString()));

                open.remove(j);

            }

            dedup(edges);

            for (int j = edges.size(); j > 0; ) {
                b = edges.get(--j);
                a = edges.get(--j);
                open.add(circumcircle(vertices, a, b, c));
            }

            edges.clear();
        }


        for (int i = (open.size() - 1); i >= 0; i--) {
            closed.add(open.get(i));
        }

        List<Integer> deltri = new ArrayList<>();
        for (int i = (closed.size() - 1); i >= 0; i--) {
            if (Integer.parseInt(closed.get(i).get("i").toString()) < n && Integer.parseInt(closed.get(i).get("j").toString()) < n && Integer.parseInt(closed.get(i).get("k").toString()) < n) {
                deltri.add(Integer.parseInt(closed.get(i).get("i").toString()));
                deltri.add(Integer.parseInt(closed.get(i).get("j").toString()));
                deltri.add(Integer.parseInt(closed.get(i).get("k").toString()));
            }
        }

        return deltri;


    }

    public List<double[]> supertriangle(List<double[]> vertices) {

        double xmin = vertices.get(0)[0];
        double ymin = vertices.get(0)[1];
        double xmax = vertices.get(1)[0];
        double ymax = vertices.get(1)[1];

        for (int i = (vertices.size() - 1); i >= 0; i--) {
            if (vertices.get(i)[0] < xmin) xmin = vertices.get(i)[0];
            if (vertices.get(i)[0] > xmax) xmax = vertices.get(i)[0];
            if (vertices.get(i)[1] < ymin) ymin = vertices.get(i)[1];
            if (vertices.get(i)[1] > ymax) ymax = vertices.get(i)[1];
        }
        double dx = xmax - xmin;
        double dy = ymax - ymin;
        double dmax = Math.max(dx, dy);
        double xmid = xmin + dx * 0.5;
        double ymid = ymin + dy * 0.5;

        List<double[]> surp = new ArrayList<>();
        surp.add(new double[]{xmid - 20 * dmax, ymid - dmax});
        surp.add(new double[]{xmid, ymid + 20 * dmax});
        surp.add(new double[]{xmid + 20 * dmax, ymid - dmax});

        return surp;

    }

    public Map circumcircle(List<double[]> vertices, int i, int j, int k) throws Exception {


        double x1 = vertices.get(i)[0],
                y1 = vertices.get(i)[1],
                x2 = vertices.get(j)[0],
                y2 = vertices.get(j)[1],
                x3 = vertices.get(k)[0],
                y3 = vertices.get(k)[1],
                fabsy1y2 = Math.abs(y1 - y2),
                fabsy2y3 = Math.abs(y2 - y3),
                xc, yc, m1, m2, mx1, mx2, my1, my2, dx, dy;

        /* Check for coincident points */
        if (fabsy1y2 < EPSILON && fabsy2y3 < EPSILON)
            throw new Exception("Eek! Coincident points!");

        if (fabsy1y2 < EPSILON) {
            m2 = -((x3 - x2) / (y3 - y2));
            mx2 = (x2 + x3) / 2.0;
            my2 = (y2 + y3) / 2.0;
            xc = (x2 + x1) / 2.0;
            yc = m2 * (xc - mx2) + my2;
        } else if (fabsy2y3 < EPSILON) {
            m1 = -((x2 - x1) / (y2 - y1));
            mx1 = (x1 + x2) / 2.0;
            my1 = (y1 + y2) / 2.0;
            xc = (x3 + x2) / 2.0;
            yc = m1 * (xc - mx1) + my1;
        } else {
            m1 = -((x2 - x1) / (y2 - y1));
            m2 = -((x3 - x2) / (y3 - y2));
            mx1 = (x1 + x2) / 2.0;
            mx2 = (x2 + x3) / 2.0;
            my1 = (y1 + y2) / 2.0;
            my2 = (y2 + y3) / 2.0;
            xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
            yc = (fabsy1y2 > fabsy2y3) ?
                    m1 * (xc - mx1) + my1 :
                    m2 * (xc - mx2) + my2;
        }

        dx = x2 - xc;
        dy = y2 - yc;
//        Map<String, Object> temp = new HashMap<String, Object>();
        Map temp = new HashMap();
        temp.put("i", i);
        temp.put("j", j);
        temp.put("k", k);
        temp.put("x", xc);
        temp.put("y", yc);
        temp.put("r", dx * dx + dy * dy);

        return temp;

    }

    public void dedup(List<Integer> edges) {
        int i, j, a, b, m, n;
        for (j = edges.size(); j > 0; ) {
            b = edges.get(--j);
            a = edges.get(--j);
            for (i = j; i > 0; ) {
                n = edges.get(--i);
                m = edges.get(--i);
                if ((a == m && b == n) || (a == n && b == m)) {
                    edges.remove(j);
                    edges.remove(j);
                    edges.remove(i);
                    edges.remove(i);
                    j = j - 2;
                    break;
                }
            }
        }
    }

    public Map<String, Double> getBound() {
        Map<String, Double> bound = new HashMap<>();
        Double minX, maxX, minY, maxY;
        minX = border.get(0).get("X");
        maxX = border.get(0).get("X");
        minY = border.get(0).get("Y");
        maxY = border.get(0).get("Y");

        for (int i = 1; i < border.size(); i++) {
            if (border.get(i).get("X") < minX) minX = border.get(i).get("X");
            if (border.get(i).get("X") > maxX) maxX = border.get(i).get("X");
            if (border.get(i).get("Y") < minY) minY = border.get(i).get("Y");
            if (border.get(i).get("Y") > maxY) maxY = border.get(i).get("Y");
        }
        bound.put("minX", minX);
        bound.put("maxX", maxX);
        bound.put("minY", minY);
        bound.put("maxY", maxY);
        return bound;
    }

    public static boolean IsPtInPoly(Point2D.Double point, List<Point2D.Double> pts) {

        int N = pts.size();
        boolean boundOrVertex = true; //如果点位于多边形的顶点或边上，也算做点在多边形内，直接返回true
        int intersectCount = 0;//cross points count of x
        double precision = 2e-10; //浮点类型计算时候与0比较时候的容差
        Point2D.Double p1, p2;//neighbour bound vertices
        Point2D.Double p = point; //当前点

        p1 = pts.get(0);//left vertex
        for (int i = 1; i <= N; ++i) {//check all rays
            if (p.equals(p1)) {
                return boundOrVertex;//p is an vertex
            }

            p2 = pts.get(i % N);//right vertex
            if (p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)) {//ray is outside of our interests
                p1 = p2;
                continue;//next ray left point
            }

            if (p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)) {//横坐标 内  ray is crossing over by the algorithm (common part of)
                if (p.y <= Math.max(p1.y, p2.y)) {//y下  x is before of ray
                    if (p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)) {//overlies on a horizontal ray  垂线
                        return boundOrVertex;
                    }

                    if (p1.y == p2.y) {//水平线 ray is vertical
                        if (p1.y == p.y) {//水平线内 overlies on a vertical ray
                            return boundOrVertex;
                        } else {//before ray
                            ++intersectCount;  //交点在上方
                        }
                    } else {//cross point on the left side
                        double xinters = (p.x - p1.x) * (p2.y - p1.y) / (p2.x - p1.x) + p1.y;//两点式化简，交点y坐标 cross point of y
                        if (Math.abs(p.y - xinters) < precision) {//== 0  在线上  overlies on a ray
                            return boundOrVertex;
                        }

                        if (p.y < xinters) {//before ray
                            ++intersectCount;  //交点在上方
                        }
                    }
                }
            } else {//special case when ray is crossing through the vertex
                if (p.x == p2.x && p.y <= p2.y) {//p crossing over p2
                    Point2D.Double p3 = pts.get((i + 1) % N); //next vertex
                    if (p.x >= Math.min(p1.x, p3.x) && p.x <= Math.max(p1.x, p3.x)) {//p.x lies between p1.x & p3.x
                        ++intersectCount;
                    } else {
                        intersectCount += 2;
                    }
                }
            }
            p1 = p2;//next ray left point
        }

        if (intersectCount % 2 == 0) {//偶数在多边形外
            return false;
        } else { //奇数在多边形内
            return true;
        }

    }
}
